#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 摆动序列：https://leetcode.cn/problems/wiggle-subsequence/description/
using namespace std;
// 状态表示：  
//             f[i]: 以i结尾的所有子序列中，长度最长的摆动序列
//             g[i]: nums[j]-nums[i]的正负状态
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n,1);
        vector<int> g(n,0);
        int ret=1;
        for(int i=1;i<n;i++)
        {
            for(int j=i;j>=0;j--)
            {
                // 一开始，区间长度<=2，由于不够3个元素，因此为无状态，此时只有两元素不等就是摆动序列，因此条件 不等&&无状态
                // 当长度足够时， 前一个状态*当前状态<0 是摆动序列
                int flag=(nums[i]!=nums[j]&&g[j]==0)||((nums[j]-nums[i])*g[j]<0);
                if(flag==1)
                {
                    f[i]=f[j]+1;
                    g[i]=nums[j]-nums[i];
                    break;
                }
            }
            ret=max(ret,f[i]);
        }
        return ret;
    }
};